#
# @lc app=leetcode.cn id=39 lang=python
#
# [39] 组合总和
#

# @lc code=start
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        self.target = target
        self.candidates = candidates
        self.result = []
        self.result_items = []
        self.loop(0)
        return self.result

    def loop(self, index):
        if sum(self.result_items) == self.target:
            self.result.append(self.result_items[:])
            return
        if sum(self.result_items) > self.target:
            return

        for i in range(max(index-1, 0), len(self.candidates)):
            self.result_items.append(self.candidates[i])
            self.loop(i+1)
            self.result_items.pop()
        
# @lc code=end

